package com.leetcode.partition9;

import java.io.*;
import java.util.LinkedList;

/**
 * @author `RKC`
 * @date 2022/1/6 9:50
 */
public class LC847访问所有节点的最短路径bfs {

    private static final int N = 13, INF = 0x3f3f3f3f;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(reader.readLine());
        int[][] graph = new int[n][];
        for (int i = 0; i < n; i++) {
            String[] s = reader.readLine().split("\\s+");
            int[] g = new int[s.length];
            for (int j = 0; j < s.length; j++) g[j] = Integer.parseInt(s[j]);
            graph[i] = g;
        }
        writer.write(shortestPathLength(graph));
        writer.flush();
    }

    public static int shortestPathLength(int[][] graph) {
        //队列，不需要使用堆，因为每一条边的权值都相等    三元组 <当前状态, 当前节点, 路径>
        LinkedList<int[]> queue = new LinkedList<>();
        //visited[i][j]记录经过j情况到达i节点是否被搜索过
        boolean[][] visited = new boolean[graph.length][1 << graph.length];
        for (int i = 0; i < graph.length; i++) {
            //对每个节点进行入队，设置当前节点已经访问
            queue.addLast(new int[]{1 << i, i, 0});
            visited[i][1 << i] = true;
        }
        while (!queue.isEmpty()) {
            int[] tuple = queue.pollFirst();
            int status = tuple[0], u = tuple[1], dis = tuple[2];
            //如果当前状态是最终全部被访问的状态，则直接返回找到的结果
            if (status == (1 << graph.length) - 1) return dis;
            //遍历其邻节点，要求状态没有重复过
            for (int v : graph[u]) {
                //如果到达邻接点后的状态没有被访问过，则进行访问
                int nextStatus = status | 1 << v;
                if (visited[v][nextStatus]) continue;
                queue.addLast(new int[]{nextStatus, v, dis + 1});
                visited[v][nextStatus] = true;
            }
        }
        return -1;
    }
}
